// The API isBadVersion is defined for you.
#include <iostream>
// bool isBadVersion(int version);
bool isBadVersion(int version)
{
    return version == 4;
}

class Solution
{
public:
    int firstBadVersion(int n)
    {
        return find(1, n);
    }
    int find(long long l, long long r)
    {
        if ((r - l) <= 1)
        {
            if (isBadVersion(l))
            {
                return l;
            }
            else if (isBadVersion(r))
            {
                return r;
            }
            else
            {
                return r + 1;
            }
        }
        if (isBadVersion((l + r) / 2))
        {
            return find(l, (l + r) / 2 - 1);
        }
        else
        {
            return find((l + r) / 2 + 1, r);
        }
    }
};
int main(int argc, char const *argv[])
{
    Solution s;
    std::cout << s.firstBadVersion(5) << std::endl;
    return 0;
}
